/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: DickYang
 * Date: 2023-07-27
 * Time: 9:13
 */
public class BinarySearchTree {
    static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;
        public  TreeNode(int val) {
            this.val = val;
        }
    }

    public TreeNode root = null;

    //查找
    public TreeNode find(int val) {
        TreeNode cur = root;
        while(cur != null) {
            if (cur.val > val) {
                cur = cur.left;
            }else if (cur.val < val) {
                cur = cur.right;
            }else {
                return cur;
            }
        }
        return null;
    }

    //插入
    public void insert(int val) {
        if (root == null) {
            root = new TreeNode(val);
            return;
        }

        TreeNode cur = root;
        TreeNode curParent = root;
        while(cur != null) {
            if (val > cur.val) {
                curParent = cur;
                cur = cur.right;
            }else if (cur.val == val) {
                return;// 二叉搜索树不用插入相同的数据,没有意义
            }else {
                curParent = cur;
                cur = cur.left;
            }
        }
        if (val > curParent.val) {
            curParent.right = new TreeNode(val);
        } else {
            curParent.left = new TreeNode(val);
        }
    }

    //中序遍历
    public void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val+ " ");
        inOrder(root.right);
    }

    //删除
    public void remove(int val) {
        if (root == null) {
            return;
        }
        TreeNode cur = root;
        TreeNode curParent = null;
        while(cur != null) {
            if (cur.val < val) {
                curParent = cur;
                cur = cur.right;
            }else if (cur.val > val) {
                curParent = cur;
                cur = cur.left;
            }else { // 找到了进行删除
                removeNode(cur,curParent);
                break;
            }
        }
    }

    private void removeNode(TreeNode cur, TreeNode curParent) {
         if (cur.left == null) {
             if (cur == root) { // 当删除节点为根
                 root = root.right;
             }else if(curParent.left == cur) { //
                 curParent.left = cur.right;
             }else {
                 curParent.right = cur.right;
             }
         }else if(cur.right == null) {
             if (cur == root) {
                 root = root.left;
             }else if(curParent.left == cur) {
                 curParent.left = cur.left;
             }else {
                 curParent.right = cur.left;
             }
         }else {
             TreeNode target = cur.right;
             TreeNode targetParent = cur;
             while(target.left != null) {
                 targetParent = target;
                 target = target.left;
             }
             cur.val = target.val;
             if (targetParent.left == target) {
                 targetParent.left = target.right;
             }else {
                 targetParent.right = target.right;
             }
         }
    }


}
